package com.ycdr.leetcode.array;

import java.util.Arrays;

/**
 * 在一个给定的数组nums中，总是存在一个最大元素 。 
 * 查找数组中的最大元素是否至少是数组中每个其他数字的两倍。
 * 如果是，则返回最大元素的索引，否则返回-1。
 * 
 * 示例 1: 
 *  输入: nums = [3, 6, 1, 0] 
 *  输出: 1 
 *  解释: 6是最大的整数, 对于数组中的其他整数,
 *       6大于数组中其他元素的两倍。6的索引是1, 所以我们返回1.
 * 
 * 示例 2: 
 * 　输入: nums = [1, 2, 3, 4] 
 * 　输出: -1 
 * 　解释: 4没有超过3的两倍大, 所以我们返回 -1.
 * 
 * @deprecated 至少是其他数字两倍的最大数
 * @author yc 颍川
 */
public class DominantIndex{

	public static void main(String[] args) {
        int[] temp=new int[]{2,0,0,1};
        
        System.out.println(dominanIndex1(temp));
    }
    /**
     * 思路分析：
     *  　1. 找出最大元素
     * 　 2. 查找是否存在最大元素-其他元素 > 其他元素　
     * @param nums
     * @return
     */
    public static int dominanIndex1(int[] nums){
        int max=nums[0];
        int maxIndex=0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>nums[maxIndex]){
                maxIndex=i;
                max=nums[i];
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if(i==maxIndex){
                continue;
            }

            if(nums[i]>max-nums[i]){
                return -1;
            }
        }
        return maxIndex;
    }

    /**
     * 思路分析：
     *  1. 找出最大元素
     *  2. 查找是否存在最大元素/其他元素 < 2 && 其他元素!=0
     * @param nums 
     * @return
     */
    public int dominantIndex11(int[] nums) {
        if (nums.length==0){return -1;}
        int max = Arrays.stream(nums).summaryStatistics().getMax();
        int maxIndex = 0;
        for (int i = 0; i <nums.length; i++) {
            if (max==nums[i]){
                maxIndex=i;
            }
        }
        for (int i = 0; i <nums.length ; i++) {
            if (nums[i]==max){continue;}
            if (nums[i]!=0&&max/nums[i]<2){
                return -1;
            }
        }
        return maxIndex;
    }


    /**
     * 思路分析：
     *  1. 找出最大元素与第二大元素
     *  2. 第二大元素>最大元素-第二大元素
     * @param nums [1, 3, 2, 4]
     * @return int
     */
    public int dominantIndex2(int[] nums) {
        if (nums.length==0){return -1;}
        int max1=0,max2=0,res=-1;
        for (int i = 0; i < nums.length; i++) {
              if(nums[i]>max1){
                  res=i;
                  max2=max1;
                  max1=nums[i];
                  continue;
              }

              if(nums[i]>max2){
                  max2=nums[i];
              }
        }

        if(max2>max1-max2){
            return -1;
        }
        return res;
    }
}